public class Num1806 {
    //给你一个偶数 n ，已知存在一个长度为 n 的排列 perm ，其中 perm[i] == i（下标 从 0 开始 计数）。
    //一步操作中，你将创建一个新数组 arr ，对于每个 i ：
    //如果 i % 2 == 0 ，那么 arr[i] = perm[i / 2]
    //如果 i % 2 == 1 ，那么 arr[i] = perm[n / 2 + (i - 1) / 2]
    //然后将 arr 赋值给 perm 。
    //要想使 perm 回到排列初始值，至少需要执行多少步操作？返回最小的 非零 操作步数。
    public int reinitializePermutation(int n) {
        int[] perm = new int[n];
        for (int i = 0; i < n; i++) {
            perm[i] = i;
        }
        boolean b = true;
        int count = 0;
        while (b) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    arr[i] = perm[i / 2];
                }else {
                    arr[i] = perm[n / 2 + (i - 1) / 2];
                }
            }
            perm = arr;
            count++;
            if (restore(perm)) b = false;
        }
        return count;
    }

    private boolean restore(int[] perm) {
        for (int i = 0; i < perm.length; i++) {
            if (perm[i] != i) return false;
        }
        return true;
    }
}
